/**
 * 数据结构作业 - 链表实现
 * 实现一个简单的单向链表
 */
public class LinkedList<T> {
    private class Node {
        T data;
        Node next;
        
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node head;
    private int size;
    
    public LinkedList() {
        head = null;
        size = 0;
    }
    
    // 在链表头部添加元素
    public void addFirst(T data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 在链表尾部添加元素
    public void addLast(T data) {
        Node newNode = new Node(data);
        
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // 删除第一个元素
    public T removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("List is empty");
        }
        
        T data = head.data;
        head = head.next;
        size--;
        return data;
    }
    
    // 获取链表大小
    public int size() {
        return size;
    }
    
    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    
    // 测试主方法
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        
        // 测试添加元素
        list.addFirst(3);
        list.addFirst(2);
        list.addFirst(1);
        list.addLast(4);
        
        System.out.println("Original list:");
        list.printList();
        
        // 测试删除元素
        Integer removed = list.removeFirst();
        System.out.println("Removed element: " + removed);
        
        System.out.println("List after removal:");
        list.printList();
        
        System.out.println("List size: " + list.size());
    }
} 